#pragma once

#include <iostream>
#include <vector>

using namespace std;

enum State
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	State _state=EMPTY;
};

template<class K,class V>
class HashTable
{

public:
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list +
			__stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

	HashTable()
	{
		_table.resize(__stl_next_prime(0));
	}

	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
		{
			return false;
		}

		if (_n * 10 / _table.size() >= 7)
		{
			HashTable<K, V> newHT;
			newHT._table.resize(__stl_next_prime(_table.size() + 1));

			for (size_t i = 0; i < _table.size(); ++i)
			{
				while (_table[i]._state == EXIST)
				{
					newHT.Insert(_table[i]._kv);
				}
			}

			_table.swap(newHT._table);
		}

		size_t hash0 = kv.first % _table.size();
		size_t hashi = hash0;
		size_t i = 1;

		while (_table[hashi]._state == EXIST)
		{
			hashi = (hash0 + i)%_table.size();
			++i;

		}

		_table[hashi]._kv = kv;
		_table[hashi]._state = EXIST;
		++_n;

		
		return true;
		
	}

	HashData<K, V>* Find(const K& key)
	{
		size_t hash0 = key % _table.size();
		size_t hashi = hash0;
		size_t i = 1;

		while (_table[hashi]._state != EMPTY)
		{
			if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
			{
				return &_table[hashi];

			}

			hashi = (hash0 + i) % _table.size();
			++i;

		}

		return nullptr;
		
	}

	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret == nullptr)
		{
			return false;
		}
		else
		{
			ret->_state = DELETE;
			--_n;
			return true;
		}
	}
private:
	vector<HashData<K, V>> _table;
	size_t _n;
};